################################################################################
#
#Copyright (c) 2011, Petr Skramovsky
#All rights reserved.
#
#Redistribution and use in source and binary forms, with or without
#modification, are permitted provided that the following conditions are met:
#    * Redistributions of source code must retain the above copyright
#      notice, this list of conditions and the following disclaimer.
#    * Redistributions in binary form must reproduce the above copyright
#      notice, this list of conditions and the following disclaimer in the
#      documentation and/or other materials provided with the distribution.
#
#THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
#ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
#WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
#DISCLAIMED. IN NO EVENT SHALL Petr Skramovsky BE LIABLE FOR ANY
#DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
#(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
#LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
#ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
#(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
#SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
################################################################################

class huffman():
  def __init__(self):
    self.hnodes = None
    self.numhnodes = [ 0 ] * 256
    self.h_used = [ 0 ] * 512
    self.h_count = [ 0 ] * 512
    self.offset = 0
    self.data = None
    self.lastnodenum = -1
    self.lastindex = -1
    self.valid = False

  def smallest_node( self, numhnodes ):
    best = 99999999
    bestnode = -1
    for i in range( 0, numhnodes ) :
      if self.h_used[ i ] :
        continue
      if self.h_count[ i ] == 0 :
        continue
      if self.h_count[ i ] < best :
        best = self.h_count[ i ]
        bestnode = i;

    if bestnode == -1 :
      return -1

    self.h_used[ bestnode ] = True
    return bestnode

  def init( self, counts ):
    node = []
    numhnodes = 0

    self.hnodes = [ 0 ] * ( 256 * 256 * 2 )

    for prev in range( 0, 256 ):
      self.h_used = [ False ] * 512
      self.h_count = [ 0 ] * 512
      for j in range( 0, 256 ):
        self.h_count[ j ] = counts[ j ][ 1 ]

      numhnodes = 256
      nodebase = 0 + prev * 256 * 2
      index = 0
      node = self.hnodes
      while numhnodes != 511 :
        index = nodebase + ( numhnodes - 256 ) * 2

        node[ index ] = self.smallest_node( numhnodes )
        if node[ index ] == -1 :
          break

        node[ index + 1 ] = self.smallest_node( numhnodes )
        if node[ index + 1 ] == -1 :
          break

        self.h_count[ numhnodes ] = self.h_count[ node[ index ] ] + self.h_count[ node[ index + 1 ] ]
        numhnodes += 1
      self.numhnodes[ prev ] = numhnodes - 1

  def decompress( self, data ):
    count = len( data )
    input = 0
    out = [ 0 ] * count
    out_p = 0

    hnodesbase = -256 * 2
    index = hnodesbase
    hnodes = self.hnodes
    nodenum = self.numhnodes[ 0 ]
    inbyte = 0
    while count != 0 :
      inbyte = ord( data[ input ] )
      input += 1

      for i in range( 0, 8 ):
        if nodenum < 256 :
          index = hnodesbase + ( nodenum << 9 )
          out[ out_p ] = nodenum
          out_p += 1
          count -= 1
          if count == 0 :
            break
          nodenum = self.numhnodes[ nodenum ]
        bit = ( inbyte & 1 )
        nodenum = hnodes[ index + nodenum * 2 + bit ]
        inbyte = inbyte >> 1

    return out


  def set_data( self, data ):
    self.data = data
    self.offset = 0
    self.lastnodenum = -1
    self.lastindex = -1
    self.valid = False

  def get_bit( self ):
    t = ( ord( self.data[ ( self.offset >> 3 ) ] ) >> ( self.offset & 7 ) ) & 0x1
    self.offset += 1
    return t

  def get_byte( self ):
    hnodesbase = -256 * 2
    hnodes = self.hnodes

    nodenum = self.numhnodes[ 0 ]
    index = hnodesbase

    value = 0

    while nodenum > 255 :
      bit = self.get_bit()
      #print "huff bit %d" % bit
      nodenum = hnodes[ index + nodenum * 2 + bit ]

    if nodenum == 247 :
      bit = self.get_bit()

    value = nodenum

    if nodenum == 129 :
      value = 10
    if nodenum == 60 :
      value = 23
    if nodenum == 218 :
      value = 25
    if nodenum == 145 :
      value = 27
    if nodenum == 154 :
      value = 27
    if nodenum == 230 :
      value = 33
    if nodenum == 62 :
      value = 34
    if nodenum == 214 :
      value = 39
    if nodenum == 185 :
      value = 43
    if nodenum == 240 :
      value = 74
    if nodenum == 166 :
      value = 81
    if nodenum == 154 :
      value = 145
    if nodenum == 244 :
      value = 157
    if nodenum == 177 :
      value = 169
    if nodenum == 220 :
      value = 203
    if nodenum == 245 :
      value = 219
    if nodenum == 249 :
      value = 219
    if nodenum == 236 :
      value = 228
    if nodenum == 249 :
      value = 245

    
    #print "huff byte %d %d" % ( value, self.offset )
    return value


